The present invention relates generally to iterative decoding, and specifically to fast iterative decoding of multiple-component codes.
Transmission of digital data is inherently prone to interference which may introduce errors into the transmitted data. Error detection schemes have been suggested to determine as reliably as possible whether errors have been introduced into the transmitted data. For example, it is common to transmit the data in packets, and add to each packet a CRC (cyclic redundancy check) field, for example of a length of 16 bits, which carries a checksum of the data of the packet. When a receiver receives the data, it calculates the same checksum on the received data and verifies whether the result of its calculation is identical to the checksum in the CRC field.
When the transmitted data is not used on-line, it is possible to request re-transmission of erroneous data when errors are detected. However, when the transmission is performed on-line such as in telephone lines, cellular phones, remote video systems, etc., it is not possible to request re-transmission.
Convolution codes have been introduced to allow receivers of digital data to correctly determine the transmitted data even when errors may have occurred during transmission. The convolution codes introduce redundancy into the data to be transmitted, forming encoded packet data and pack the transmitted data into packets in which the value of each bit is dependent on earlier bits in the sequence. Thus, when a few errors occur, the receiver can still deduce the original data by tracing back possible sequences in the received data.
To further improve the performance of a transmission channel, some coding schemes include interleavers, which mix up the order of the bits in the packet during coding. Thus, when interference destroys a few adjacent bits during transmission, the effect of the interference is spread out over the entire original packet and can more readily be overcome by the decoding process. Other improvements may include multiple-component codes which include coding the packet more than once in parallel or in series. For example, U.S. Pat. No. 5,446,747, which is incorporated herein by reference, describes an error correction method using at least two convolutional codings in parallel. Such parallel encoding is known in the art as xe2x80x9cTurbo coding.xe2x80x9d
For multiple component codes, optimal decoding is often a very complex task, and may require large periods of time, not usually available for on-line decoding. In order to overcome this problem, iterative decoding techniques have been developed. Rather than determining immediately whether received bits are zero or one, the receiver assigns each bit a value on a multi-level scale representative of the probability that the bit is one. A common scale, referred to as LLR probabilities, represents each bit by an integer in the range {xe2x88x9232, 31}. The value of 31 signifies that the transmitted bit was a zero with very high probability, and the value of xe2x88x9232 signifies that the transmitted bit was a one, with very high probability. A value of zero indicates that the value is indeterminate.
Data represented on the multi-level scale is referred to as xe2x80x9csoft data,xe2x80x9d and iterative decoding is usually soft-in/soft-out, i.e., the decoding process receives a sequence of inputs corresponding to probabilities for the bit values and provides as output corrected probabilities taking into account constraints of the code. Generally, a decoder which performs iterative decoding, uses soft data from former iterations to decode the soft data read by the receiver. A method of iterative decoding is described, for example, in U.S. Pat. No. 5,563,897, which is incorporated herein by reference.
During iterative decoding of multiple-component codes, the decoder uses results from decoding of one code to improve the decoding of the second code. When parallel encoders are used, as in Turbo coding, two corresponding decoders may conveniently be used in parallel for this purpose.
The iterative decoding is carried out for a plurality of iterations until it is believed that the soft data closely represents the transmitted data. Those bits which have a probability indicating that they are closer to zero (for example, between 0 and 31 on the scale described above) are assigned binary zero, and the rest of the bits are assigned binary one.
Generally, the iterative process is repeated a predetermined number of times. According to xe2x80x9cAn Introduction to Turbo Codes,xe2x80x9d by Matthew C. Valenti, which can be found at lamarr.mprg.ee.vt.edu/documents/turbo.pdf and is incorporated herein by reference, the predetermined number of iterations is about 18. However, this article further states that in many cases as few as 6 iterations can provide satisfactory performance. xe2x80x9cIterative Decoding of Binary Block Codes,xe2x80x9d by Joachim Hagenauer, Elke Offer and Lutz Papke, IEEE Trans. of Information Theory, Vol. 42, No. 2, pp. 429-445 (March 1996), which is incorporated herein by reference, suggests using a cross entropy criteria to determine when to stop the iterative decoding process individually for each packet. Thus, the calculation power of a decoder may be used more efficiently than when all packets are decoded using the same number of iterations. However, the cross entropy criterion is in itself very complex, reducing substantially the gain in efficiency in applying variable numbers of iterations.
In one commonly-used multiple-component coding scheme, the packet is first encoded by a first xe2x80x9couterxe2x80x9d coding scheme. Thereafter, it is interleaved and is then encoded by a second xe2x80x9cinnerxe2x80x9d coding scheme. During decoding, the inner code is first decoded, the result is de-interleaved, and then the outer code is decoded. The results of decoding the outer code are thereafter used in a second iteration of decoding the inner code to improve its results. This process is continued iteratively until the coded packet is satisfactorily decoded.
The above-described decoding scheme is typically implemented by a single hardware decoder, which alternately decodes the inner and outer codes. However, when very fast decoding is needed, and the inner and outer codes are substantially different, the computational load is generally beyond the capability of a single decoder of conventional design. Therefore, it has been suggested to use a decoder including two processors, one for the inner code and one for the outer code. However, this results in having each of the processors idle half of the time, while it waits for results from the other processor.
It is an object of some aspects of the present invention to provide methods and apparatus for fast iterative decoding of codes based on two or more different convolutional encoding schemes.
It is another object of some aspects of the present invention to provide apparatus for efficient iterative decoding of convolution codes.
It is a further object of some aspects of the present invention to provide an efficient method for determining how many iterations are needed for reliable decoding of a packet.
In preferred embodiments of the present invention, the decoding time allotted for decoding each code in a multi-code series or parallel coding scheme is made substantially equal. A decoder including two processors receives two packets of data in sequence and decodes them simultaneously. While one packet is being decoded in a first processor, the second processor decodes the second packet. When both processors finish a single iteration, the packets are switched between the processors, and another iteration is performed. Thus, both processors are substantially constantly in use, and codes may be decoded twice as fast as in prior art schemes of comparable hardware complexity. Preferably, both processors operate concurrently at least 50% of their operation time on any input packet.
In some preferred embodiments of the present invention, the two packets are decoded independently of each other, so that termination of decoding of the packets is independent. When a first packet is finished being decoded, a new packet may enter one of the decoders, regardless of whether the second packet has finished being decoded.
In some preferred embodiments of the present invention, the multicode scheme includes an inner coding scheme and an outer coding scheme. Preferably, the inner and outer coding schemes are chosen such that the decoding time of a single iteration of both of them is approximately the same. Alternatively or additionally, the processor that finishes an iteration first waits for the second processor to finish processing, and then the packets are switched between the decoders. Preferably, the inner and outer coding schemes are different and cannot easily be decoded by the same processor.
In another aspect of the present invention, during decoding of each packet, a simple method is used for determining when to stop the iterative process. A termination checking procedure is preferably performed after substantially each iteration, and includes determining a minimal absolute probability value associated with any of the bits in the packet. When the minimal absolute probability value is above a predetermined threshold, indicating that all of the bits have been assigned either the value xe2x80x9c1xe2x80x9d or xe2x80x9c0xe2x80x9d with relatively high probability, the iterative process is terminated.
Alternatively or additionally, each packet is transmitted with a CRC field. After each decoding iteration, the termination checking procedure checks whether the CRC value computed from the data to be output from that iteration is compatible with the CRC field. Preferably, the checking procedure checks the CRC field only when the minimal probability value is above the threshold. If the CRC field is compatible with the extracted data, the iteration procedure is terminated.
In some preferred embodiments of the present invention, the checking procedure begins only after a minimal initial number of iterations, in order to reduce the probability of the CRC check returning an apparently xe2x80x9ccorrectxe2x80x9d result although the decoded data is incorrect. Preferably, the minimal number of iterations is between four and eight. The number of iterations is preferably chosen to be a number of iterations which for most packets does not bring the minimal probability value above the threshold. Further preferably, the iterative process is terminated after a maximal number of iterations regardless of any other conditions. Preferably, the maximal number of iterations is between 20 and 30.
In other preferred embodiments of the present invention, the minimal absolute probability value may be replaced by an average probability value, by a median probability value, or by any other value indicative of the progress of the iterative decoding process. For example, when it is desired to minimize a Bit Error (BER) criterion rather than a packet error rate, the minimal absolute value is preferably replaced by a next-to-minimum value, i.e., the lowest value after ignoring one or two exceptions.
There is therefore provided in accordance with a preferred embodiment of the present invention, apparatus for iterative decoding of a sequence of signal packets coded in accordance with a multi-component coding scheme, including a plurality of decoders, each of which performs a respective different decoding method on one of the signal packets, such that the plurality of decoders operate substantially concurrently.
Preferably, the plurality of decoders operate concurrently on different, respective packets.
Preferably, the plurality of decoders operate concurrently during at least 50% of the operation time during which the apparatus decodes the sequence.
Further preferably, the plurality of decoders operate concurrently during substantially the entire operation time of the apparatus.
Preferably, each of the plurality of decoders receives as its input a packet processed by another one of the plurality of decoders in most of the iterations.
Preferably, the plurality of decoders includes two decoders.
Preferably, the apparatus further includes a plurality of memory units to which the decoders output the packets after decoding.
Preferably, the packets are interleaved or de-interleaved after decoding.
Preferably, each of the plurality of decoders requires a generally equal decoding time to that of the other decoders.
Preferably, the multi-component coding scheme includes a parallel coding scheme.
Alternatively, the multi-component coding scheme includes a serial coding scheme.
Preferably, the plurality of decoders includes APP decoders.
There is further provided in accordance with a preferred embodiment of the present invention, a method of decoding a sequence of packets of data, coded in accordance with a multi-component coding scheme including inner and outer codes, including decoding a first packet in a first decoder, which decodes the inner code to generate a first decoded output packet, and decoding the first decoded output packet in a second decoder, which decodes the outer code, while substantially concurrently decoding a second packet in the first decoder.
Preferably, the method includes outputting the first packet from the second decoder to the first decoder, so as to repeat decoding the inner code.
Preferably, the method includes repeatedly decoding the first and second packets in the first and second decoders in alternation.
Preferably, the method includes de-interleaving the first output packet before decoding it in the second decoder.
Preferably, the multi-component coding scheme includes a serial coding scheme.
There is further provided in accordance with a preferred embodiment of the present invention, in a system for iterative decoding of a packet of soft data in which each bit is represented by a probability value, a method for determining after which of a plurality of iterations to terminate the decoding, including determining a probability value of the bits in the packet, and deciding to terminate the decoding only if the probability value is above a predetermined value.
Preferably, determining the probability value includes determining a minimal probability of the hard data values of the bits in the packet.
Preferably, determining the minimal probability value includes determining a minimal absolute log probability value.
Preferably, the method includes verifying that an error detection field in the packet is correct, and deciding to terminate includes deciding to terminate only if the error detection field is correct.
Preferably, the process of verifying that the error detection field is correct is performed when the probability value is above the predetermined value.
Preferably, the process of determining the probability value is performed only after a predetermined number of decoding iterations have been performed on the packet.
Preferably, determining the probability value includes determining the probability value on a decoded copy of the bits in the packet.
Alternatively or additionally, determining the probability value includes determining the probability value on a coded copy of the bits in the packet.
There is further provided in accordance with a preferred embodiment of the present invention, apparatus for iterative decoding of coded packets including for each bit a probability value, including a decoder which performs iterations of decoding the packet, and a control unit which determines whether an additional iteration is to be performed by the decoder responsive to the probability values of the bits in the packet.
Preferably, the control unit causes the decoder to perform a predetermined number of iterations without checking the packet.
Preferably, the control unit determines whether an additional iteration is to be performed by the decoder responsive to an error detection field in the packet if the probability values fulfill a predetermined condition.
Preferably, the control unit does not initiate an additional iteration by the decoder if the error detection field is correct.
Preferably, the decoder includes an APP decoder.
Preferably, the control unit calculates a minimal probability of the hard data values of the bits in the packet and determines whether an additional iteration is to be performed responsive to the minimal probability.
Further preferably, the control unit calculates a minimal absolute log probability value.
Preferably, the control unit calculates the minimal probability based on a probability value of either a decoded or coded copy of the packet.
The present invention will be more fully understood from the following detailed description of the preferred embodiments thereof, taken together with the drawings, in which: